package day01;


import java.util.Arrays;

/**
 * @author wang hao
 * @date 2023-02-19 15:07
 *  归并排序
 *      原理：先让左半部分有序，再让右半部分有序
 *
 */
public class MergeSort {


    public static void sort(int[] nums) {
        process(nums, 0, nums.length - 1);
    }

    private static void process(int[] nums, int L, int R) {
        if (L >= R) return;
        int mid = L + ((R -L) >> 1);
        process(nums, L, mid);
        process(nums, mid + 1, R);
        merge(nums, L, mid, R);
    }

    private static void merge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r - l + 1];

        int i = 0;
        int p1 = l;
        int p2 = mid + 1;


        while (p1 <= mid && p2 <= r){
            if (arr[p1] > arr[p2]){
                help[i] = arr[p2];
                i++;
                p2++;
            }else  {
                help[i] = arr[p1];
                i++;
                p1++;
            }
        }
        while (p1 <= mid){
            help[i] = arr[p1];
            p1++;
            i++;
        }

        while (p2 <= r){
            help[i] = arr[p2];
            p2++;
            i++;
        }

        for (int j = 0; j < help.length; j++) {
            arr[l + j] = help[j];
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,3,4,5,6};
        MergeSort.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
